package com.datastructures2.字符串;

/**
 * @author MaoLin Wang
 * @date 2020/10/6 10:59 上午
 */
public class 最长回文子串 {

    /**
     * 中心扩散法
     *
     * @param str
     * @return
     */
    public static String solution1(String str) {
        if (str == null || "".equals(str)) {
            return "";
        }
        if (str.length() == 1) {
            return str;
        }
        if (str.length() == 2) {
            return str.charAt(0) == str.charAt(1) ? str : "";
        }
        int begin = 0;
        int maxLen = 0;
        char[] charArray = str.toCharArray();
        for (int i = 0; i < str.length()-1; i++) {
            int oddLen = middleExpend(charArray, i, i);
            int evenLen = middleExpend(charArray, i, i + 1);

            int len = Math.max(oddLen, evenLen);
            if (len > maxLen) {
                maxLen = len;
                begin = i - (len - 1) / 2;
            }
        }
        return str.substring(begin, begin + maxLen);
    }

    private static int middleExpend(char[] charArray, int i, int j) {
        int len = charArray.length;
        int left = i;
        int right = j;

        while (left >= 0 && right < len) {
            if (charArray[left] == charArray[right]) {
                left--;
                right++;
            } else {
                break;
            }
        }
        return right - left - 1;
    }

    /**
     * 动态规划
     * @param str
     * @return
     */
    public static String solution2(String str){
        if (str==null || "".equals(str)){
            return "";
        }
        if (str.length()==1){
            return str;
        }
        int len=str.length();
        boolean[][] dp=new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i]=true;
        }

        int maxLen=1;
        int begin=0;
        for (int j = 1; j < len ; j++) {
            for (int i = 0; i < j; i++) {
                if (str.charAt(i)!=str.charAt(j)){
                    dp[i][j]=false;
                }else {
                    if (j-i < 3){
                        dp[i][j]=true;
                    }else {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if (dp[i][j] && maxLen<j-i+1){
                    maxLen=j-i+1;
                    begin=i;
                }
            }
        }
        return str.substring(begin,begin+maxLen);


    }
    public static void main(String[]args) {
        System.out.println(solution2("aabbaacc"));
    }
}
